package sortAlgorithm;

import java.util.HashSet;
import java.util.Set;

/**
 * 快排伪代码<p>
 *
 * // 快速排序，A是数组，n表示数组的大小<p>
 * quick_sort(A, n) {<p>
 *   &nbsp quick_sort_c(A, 0, n-1)<p>
 * }<p>
 * // 快速排序递归函数，p,r为下标<p>
 * quick_sort_c(A, p, r) {<p>
 * &nbsp if p >= r then return<p>
 *
 * &nbsp q = partition(A, p, r) // 获取分区点<p>
 * &nbsp quick_sort_c(A, p, q-1)<p>
 * &nbsp quick_sort_c(A, q+1, r)<p>
 * }
 */
public class QuickSort {

  public static void quickSort(int[] nums) {
    if (nums == null || nums.length <= 1) {
      return;
    }
    quickSort(nums, 0, nums.length - 1);
  }

  private static void quickSort(int[] nums, int startIndex, int endIndex) {
    if (startIndex >= endIndex) {
      return;
    }
    //分区之后，[startIndex, pIndex - 1]范围内的数值都小于nums[pIndex],
    //[pIndex + 1, endIndex]范围内的数值都大于nums[pIndex]
    int pIndex = partition1(nums, startIndex, endIndex);
    //注意，再次排序的时候，不要包含pIndex，否则会陷入死循环
    quickSort(nums, startIndex, pIndex - 1);
    quickSort(nums, pIndex + 1, endIndex);
  }

  /**
   * 原地分区函数，不使用额外空间
   * @param nums
   * @param startIndex
   * @param endIndex
   * @return
   */
  private static int partition1(int[] nums, int startIndex, int endIndex) {
    int pivotIndex = endIndex;
    int i, j;
    for (i = startIndex, j = startIndex; j < endIndex; ++j) {
      if (nums[j] < nums[pivotIndex]) {
        swapArray(nums, i, j);
        ++i;
      }
    }
    swapArray(nums, i, pivotIndex);
    pivotIndex = i;
    return pivotIndex;
  }

  /**
   * 非原地分区，需要额外使用空间
   * @param nums
   * @param start
   * @param end
   * @return
   */
  private static int partition2(int[] nums, int start, int end) {
    // 首先选取最后一个下标作为分区点
    int pivot = end;
    int[] tmp = new int[end - start + 1];
    int i = 0;
    Set<Integer> set = new HashSet<>();
    // 将元素值小于等于分区点所对应的元素放入tmps这个数组
    for (int j = start; j <= (end - 1); ++j) {
      if (nums[j] <= nums[pivot]) {
        tmp[i++] = nums[j];
        set.add(j);
      }
    }
    // i一方面记录了tmp中元素插入的位置，一方面还记录了除了nums[pivot]本身以外，
    // [start, end]区间范围内小于等于nums[pivot]元素的个数
    pivot = start + i;
    tmp[i++] = nums[end];
    for (int k = start; k <= (end - 1); ++k) {
      if (!set.contains(k)) {
        tmp[i++] = nums[k];
      }
    }
    i = 0;
    for (int m = start; m <= end; ++m) {
      nums[m] = tmp[i++];
    }
    return pivot;
  }
  private static void swapArray(int[] nums, int indexI, int indexJ) {
    int tmp = nums[indexI];
    nums[indexI] = nums[indexJ];
    nums[indexJ] = tmp;
  }
}
